package acwing_05;
import java.io.*;
import java.util.*;
public class _898_线性DP_数字三角形 {
	//	样例
	//	5
	//	7
	//	3 8
	//	8 1 0 
	//	2 7 4 4
	//	4 5 2 6 5
	/*
	 * 思路：
	 * 题目给出的是求数字三角形的最大路径，每次只能走左下方或者右上方，那么最大路径就是从头走到底
	 * 那么实际是求[1][1]往下走的最大值，[1][1]的最大值实际是其左下角的最大值或右下角的最大值 再加上当前路径路径[1][1]的值
	 * 左下角的最大值又是该左下角的最大值和右下角的最大值 再加当前位置的路径值，依此类推
	 * 最终我们可以转化为从底部路径往上走，走到指定位置时，就取左下角和右下角其一最大值，就是当前位置的最大值
	 * 通过不断从下往上汇总，就能得到[1][1]的最大值，即路径的最大值
	 * */
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int N = 510;
	static int n;
	static int r[][] = new int[N][N];
	static int dp[][] = new int[N][N];
	public static void main(String[] args) throws IOException {
		
		n = Integer.parseInt(br.readLine());
		
		for(int i = 1; i <= n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 1; j <= i; j++) {
				r[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		// 将最底部的数值初始化成自己
		for(int i = 1; i <= n; i++) {
			dp[n][i] = r[n][i];
		}
		// 从底部开始，dp[i][j]的值为 左下角+d[i][j]自身路径值 右下角+d[i][j]自身路径值 两者取其中一个最大值
		for(int i = n-1; i >= 1; i--) {
			for(int j = 1; j <= i; j++) {
				// 左下角加上当前路径的值：dp[i+1][j] + r[i][j]
				// 右下角加上当前路径的值：dp[i+1][j+1] + r[i][j]
				dp[i][j] = Math.max(dp[i+1][j] + r[i][j], dp[i+1][j+1] + r[i][j]);
			}
		}
		
		// 最终dp[1][1]拿到的是其左下角的最大路径值，右下角的最大路径值，两者取一最大值就是最长路径值
		System.out.println(dp[1][1]);
	}
}
